#include<bits/stdc++.h> 
using namespace std;
//	杭州为游客提供了方便的公共自行车服务，一个人可以在任意一个站借车与还车。
//	PBMC实时监控所有站点的自行车容量。一个站点最好的状况是刚好有一半的车子在，
//	如果有某个站点车子满了或者空了，PBMC会收集一些自行车然后送到其他站点来维持
//	完美状态。而且所有站点都会被调整。当一个问题站点出现了，PBMC会挑选最短路径
//	来到达这个站点，如果有多条最短路，则需要输送从PBMC最少量自行车的那条更好。
//	现在给定每个站点最大车辆数为10，用图来表示PBMC与各个站点之间的通路，题目给
//	的图有两种做法，第一种是PBMC带着4辆车，然后从S1顺1辆车，这样S1和S3都完美了
//	第二种是从PBMC带着3辆车，然后从S2顺2辆车，这样S2和S3都完美了。由于两条路径
//	的距离是一样的，走S2的话可以从本部少拿点出来，所有走第二种方法。
//1.每个输入有一个测试用例。对于一个用例，分为三部分。第一行由4个数字组成。
//	Cmax≤100的偶数，表示每个站点最大的容量；N≤500，表示车站总数；Sp表示有问题
//	的车站的编号；以及M表示道路的数量
//2.接下来第二部分，在一行内有N个非负整数，表示各个站点的车数
//3.第三部分紧跟M行，每一行分别由Si，Sj和Tij组成，表示i站和j站之间要花Tij来走
//4.对于测试用例需要在一行内输出，首先输出需要从PBMC本部带出的数量，然后用空格
//	隔开，输出从本部到出问题的Sp的路线，如0->S1->S2...->Sp，最后用空格隔开，跟
//	进一个需要从该站点带回PBMC的数量。
//5.无向图Dijkstra算法求最短路径，DFS找到拿取最少的路径 
int roads[501][501];	//存储无向图的二维矩阵，存的是两个站点的距离 
int dist[501];	//存储起始点到某个站点的距离 
int capacity[501]; 	//存储每个站点的当前车容量 
bool visited[501];	//存储每个站点在Dij算法中是否被访问过 
vector<int> bestRoad, road;	//最优路径以及DFS中用到的临时路径 
vector<int> preNode[501];	//每个结点存储从起点到该结点的最优路线族中的前置结点 
int C_max, N, S_p, M;
int inf = 0x3f3f3f3f;	//定义一个最大数 
int min_send = inf, min_collect = inf;	//初始化最小拿取量为最大值 
void DFS(int now){	//DFS算法，用递归的思想，通过Dij算法后得到了每个结点的最优前置结点集合，通过从终点开始往起点走的思想，一直往前递归，直到走到起点为止 
	if(now==0){	//如果走到起点了 
		road.push_back(now);	//把起点压入向量（这里的向量可用栈代替） 
		int send = 0, collect = 0;	//定义临时拿取数量 
		for(int i =road.size()-2;i>=0;i--){	//从起点往终点开始复盘，由于起点的情况特殊，所以直接从下一个结点开始考察 
			if(capacity[road[i]]+collect<C_max/2) //如果该结点的车数和我从前面结点顺过来的车数和仍然小于完美车数 
			{
				send += C_max / 2 - (capacity[road[i]] + collect);	//则本部需要向它派送的车数就要增加 
				collect = 0;	//前面顺过来的车数清空 
			}
			else{	//否则，该站点车子够多 
				if(capacity[road[i]]<C_max/2){	//如果这个站点本身车数就超过完美车数了，则我再顺几辆走 
					collect -= (C_max / 2 - capacity[road[i]]);
				}
				else{	//否则我就填补到完美车辆为止 
					collect += capacity[road[i]] - C_max / 2;
				}
			}
		}
		if(send < min_send){	//如果这条路所需要本部拿出的车数小于已知最优路的 
			bestRoad = road;	//这条就是目前的最优路，然后最小数就交换一下 
			min_send = send;
			min_collect = collect;
		}
		else if(send == min_send && collect < min_collect) {	//如果拿数相同，则搬回来的车数少的也行 
			bestRoad = road;
			min_collect = collect;
		}
		road.pop_back();	//弹出起点结点 
		return;	//返回上一层 
	}
	road.push_back(now);	//否则的话压入该结点 
	for(int i = 0;i<preNode[now].size();i++) DFS(preNode[now][i]);	//把这个结点的最优前驱结点都DFS一下 
	road.pop_back();	//弹出该结点，返回上一层 
	return;
}
void dijkstra(){
	fill(dist, dist+N+1,inf);	//初始化所有的距离都是最大的 
	fill(visited,visited+N+1,false);	//初始化所有的结点都没访问过 
	dist[0] = 0;	//起点到自己的距离为0 
	while(true){
		int min_dis = inf;	//最小距离设置为最大 
		int min_index = -1;	//这轮的最近结点为-1 
		for(int i =0;i<=N;i++){
			if(visited[i]==false && dist[i]<min_dis){	//如果这个结点没有被遍历过，从起点到这个点的距离比最小距离小 
				min_dis = dist[i];	//则这个是最小距离 
				min_index = i;	//这个是最近结点 
			}
		}
		if(min_index == -1) return;	//如果没有没被遍历到的最小结点，则算法处理完毕，返回 
		visited[min_index] = true;	//否则，该最近结点设置为已访问状态 
		for(int i=0;i<=N;i++){
			if(visited[i]==false && roads[min_index][i]!=inf){	//如果某个结点没有被访问过，且该结点到最近点之间有通路 
				if(dist[min_index]+roads[min_index][i]<dist[i]){	//如果从起点到最近点的距离+这个点到最近点的距离<起点到这个点的距离 
					dist[i] = dist[min_index]+roads[min_index][i];	//则这个点到起点的距离就是两者之和 
					preNode[i].clear();	//情况该结点之前一切的前驱结点 
					preNode[i].push_back(min_index);	//把最近结点压入 
				}
				else if(dist[min_index]+roads[min_index][i]==dist[i]){	//如果一样近 
					preNode[i].push_back(min_index);	//则该最近结点也压入 
				}
			}
		}
	}
}
int main(){
	cin>>C_max>>N>>S_p>>M;
	capacity[0] = 50000;
	for(int i = 1;i<N+1;i++){
		cin>>capacity[i];	//读入站点容量 
	}
	fill(roads[0],roads[0]+251001,inf);	//初始化每条路的距离为最大值 
	for(int i =0;i<M;i++){
		int ci, cj, tij;
		cin>>ci>>cj>>tij;
		roads[ci][cj]=tij;
		roads[cj][ci]=tij;
	}
	dijkstra();
	DFS(S_p);
	cout<<min_send<<" ";
	for(int i = bestRoad.size()-1;i>=0;i--){
		cout<<bestRoad[i];
		if(i==0) cout<<" ";	//如果是输出到最后一个了就输出空格，否则→ 
		else cout<<"->";
	}
	cout<<min_collect<<endl;
	return 0;
} 

